In modern multilabel classification problems, each data instance belongs to a small number of classes among a large set of classes. In other words, these problems involve learning very sparse binary label vectors. Moreover, in the large-scale problems, the labels typically have certain (unknown) hierarchy. In this paper we exploit the sparsity of label vectors and the hierarchical structure to embed them in low-dimensional space using label groupings. Consequently, we solve the classification problem in a much lower dimensional space and then obtain labels in the original space using an appropriately defined lifting.

The authors introduce a method for speeding up a group testing approach for multi-label classification. Thanks to this, the new algorithm can be used for problems with a large number of labels. The paper is clearly written. Some reviewers were underlining the incremental contribution, but majority of them agreed with the authors that improving complexity of the existing solution is a sufficient contribution. The authors should, however, revise their discussion on the complexity of clustering methods used by the label tree approaches.

In modern multilabel classification problems, each data instance belongs to a small number of classes among a large set of classes. In other words, these problems involve learning very sparse binary label vectors. Moreover, in the large-scale problems, the labels typically have certain (unknown) hierarchy. In this paper we exploit the sparsity of label vectors and the hierarchical structure to embed them in low-dimensional space using label groupings. Consequently, we solve the classification problem in a much lower dimensional space and then obtain labels in the original space using an appropriately defined lifting.